﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Hard_41_FirstMissingPositive
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine(FirstMissingPositive(new int[] {3,4,-1,1 }));
            Console.ReadKey();
        }
        public static int FirstMissingPositive(int[] nums)
        {
            //不能排序，不能数组
            #region 不满足条件，哈希表空间复杂度不满足
            //int index = 1;
            //Array.Sort(nums);
            //HashSet<int> hash = new HashSet<int>(nums);
            //foreach (var item in hash)
            //{
            //    if (item > 0)
            //    {
            //        if (index == item)
            //        {
            //            index++;
            //            continue;
            //        }
            //        else break;
            //    }
            //}
            //return index;
            #endregion

            #region 数组模拟哈希表

            //1.把数组中小于零的换成n+1
            //3.遍历数组。当读到数字a时，给第a-1位的元素加上符号
            //4.再次遍历数组。返回第一个正数元素的下标+1
            //5.如果之前的步骤中没有发现nums中有正数元素，则返回n+1
            //int n = nums.Length;
            //for (int i = 0; i < nums.Length; i++) if (nums[i] <= 0) nums[i] = n + 1;

            //for (int i = 0; i < nums.Length; i++)
            //{
            //    int num = Math.Abs(nums[i]);
            //    if (num <= n) nums[num - 1] = -Math.Abs(nums[num - 1]);
            //}

            //for (int i = 0; i < nums.Length; i++) if (nums[i] > 0) return i + 1;
            //return n + 1;

            #endregion

            #region 置换
            int n = nums.Length;

            //报错
            for (int i = 0; i < nums.Length; i++)
            {
                while (0 < nums[i] && nums[i] < n && nums[i] != nums[nums[i] - 1])
                {
                    int temp = nums[nums[i] - 1];
                    nums[nums[i] - 1] = nums[i];
                    nums[i] = temp;
                }
            }

            for (int i = 0; i < nums.Length; i++) if (nums[i] != i + 1) return i + 1;
            return n+1;

            #endregion
        }
    }
}
